from .priority_queue_base import PriorityQueueBase
from .doublylinked_positional_list import PositionalList


class SortedPriorityQueue(PriorityQueueBase):
    """A min-oriented priority queue implemented with a sorted list"""
    def __init__(self):
        """Create an empty priority queue"""
        self._data = PositionalList()

    def __len__(self):
        return len(self._data)

    def __str__(self):
        data = []
        walk = self._data.first()
        while walk is not None:
            item = walk.element()
            data.append((item._key, item._value))
            walk = self._data.after(walk)
        return str(data)

    def add(self, key, value):
        """Add key-value pair"""
        new_item = self._Item(key, value)
        walk = self._data.last()

        while walk is not None and new_item < walk.element():
            walk = self._data.before(walk)

        if walk is None:
            self._data.add_first(new_item)
        else:
            self._data.add_after(walk, new_item)

    def min(self):
        """Return but not remove minimun key"""
        if self.is_empty():
            raise Exception("Priority queue is empty")
        p = self._data.first()
        item = p.element()
        return (item._key, item._value)

    def remove_min(self):
        if self.is_empty():
            raise Exception("Priority queue is empty")
        item = self._data.delete(self._data.first())
        return (item._key, item._value)